<script setup>
import { computed, nextTick, onMounted, ref, watch } from 'vue';

const props = defineProps({
  cellWidth: {type: Number, required: true, 'default': 10},
  cellHeight: {type: Number, required: true, 'default': 10},
  boxWidth: {type: Number, required: true, 'default': 900},
  boxHeight: {type: Number, required: true, 'default': 900},
  elementMaxWidth: {type: Number, required: true, 'default': 900},
  data: {type: Array, required: true},
  deepth: {type: Number, default: 10},
  grid: {type: Boolean, default: false}
})

const emit = defineEmits(['onLayout'])
let rows = props.boxHeight / props.cellHeight
let columns = props.boxWidth / props.cellWidth
let result_table = gen_empty_table(rows, columns)
const referBox = ref()
const refer = ref()
const nodes = ref([])
const canvas = ref(document.createElement('canvas'))
const showGrid = ref(props.grid)

const canvasWidth = computed(() => {
  return props.boxWidth * window.devicePixelRatio
})
const canvasHeight = computed(() => {
  return props.boxHeight * window.devicePixelRatio
})

/**
 * 测量文本尺寸
 * @param str String
 */
function measure(str = "", maxWidth=0) {
  const maxW = Math.min(Math.max(maxWidth, props.elementMaxWidth), props.boxWidth - 10)
  refer.value.style.maxWidth = `${maxW}px`
  refer.value.textContent = str
  const width = referBox.value.offsetWidth + 2
  const height = referBox.value.offsetHeight + 2
  const rows = Math.ceil(height / props.cellHeight)
  const columns = Math.ceil(width / props.cellWidth)
  return {
    text: str, width, height,
    left: -1, top: -1,
    rows, columns,
    leftPx: -1, topPx: -1,
    maxW,
    overlap: false,
    done: false
  }
}

function is_empty(table = [[]], startLine = 0, startColumn = 0, row = 0, col = 0) {
  for (let r = startLine; r < startLine + row; r++) {
    if (r >= table.length) return false
    for (let c = startColumn; c < startColumn + col; c++) {
      if (c >= table[r].length) return false
      if (table[r][c] > 0) {
        return false
      }
    }
  }

  return true
}

/**
 * 以行优先的方式进行查找目标left以及top，可扩展出列优先的方式
 * @param table 待查找的表
 * @param col 目标列数
 * @param row 目标行数
 * @param direction 方向, 0 - 左上角开始，行优先; 1 - 左下角开始，行优先; 2 - 右上角开始，行优先；3 - 右下角开始，行优先；
 */
function find_lt(table = [[]], col = 0, row = 0, direction=-1) {
  let targetRow = -1, targetCol = -1
  direction = direction == -1 ? Math.floor(Math.random() * 4) : direction
  if (direction == 3) {
    for (let r = table.length - row; r >= 0; r--) {
      for (let c = table[r].length - col; c >= 0; c--) {
        if (is_empty(table, r, c, row, col)) {
          targetRow = r, targetCol = c
          break
        }
      }
      if (targetRow > -1) {
        break
      }
    }
  } else if(direction == 2) {
    for (let r = 0; r < table.length - (row - 1); r++) {
      for (let c = table[r].length - col; c >= 0; c--) {
        if (is_empty(table, r, c, row, col)) {
          targetRow = r, targetCol = c
          break
        }
      }
      if (targetRow > -1) {
        break
      }
    }
  } else if (direction == 1) {
    for (let r = table.length - row; r >= 0; r--) {
      for (let c = 0; c < table[r].length - (col - 1); c++) {
        if (is_empty(table, r, c, row, col)) {
          targetRow = r, targetCol = c
          break
        }
      }
      if (targetRow > -1) {
        break
      }
    }
  } else if (direction == 0) {
    for (let r = 0; r < table.length - (row - 1); r++) {
      for (let c = 0; c < table[r].length - (col - 1); c++) {
        if (is_empty(table, r, c, row, col)) {
          targetRow = r, targetCol = c
          break
        }
      }
      if (targetRow >= 0 && targetCol >= 0) {
        break
      }
    }
  }
  
  return { top: targetRow, left: targetCol }
}

/**
 * 判断两张表是否有交叉
 */
function is_cross_over(table1 = [[]], table2 = [[]]) {
  for (let i = 0; i < table1.length; i++) {
    for (let j = 0; j < table1[i].length; j++) {
      const one = table1[i][j], two = table2[i][j]
      if (one > 0 && two > 0) {
        return true
      }
    }
  }
  return false
}

/**
 * 生成一个二维数组
 * @param maxRow 共多少行
 * @param maxColumn 共多少列
 */
function gen_empty_table(maxRow = 0, maxColumn = 0) {
  const table = []
  for (let i = 0; i < maxRow; i++) {
    const inner = [...new Array(maxColumn).fill(0)]
    table.push(inner)
  }
  return table
}

function gen_layout_table(rows = 0, columns = 0, maxRow = 0, maxColumn = 0, value = 1) {
  const deltaRow = maxRow - rows, deltaCol = maxColumn - columns
  const table = gen_empty_table(maxRow, maxColumn)
  const randomRow = Math.floor(Math.random() * deltaRow % deltaRow)
  const randowCol = Math.floor(Math.random() * deltaCol % deltaCol)
  fill_rect(table, randowCol, randomRow, rows, columns, value)
  return {left: randowCol, top: randomRow, table}
}

function merge_table(table1, table2) {
  for (let i = 0; i < table1.length; i++) {
    for (let j = 0; j < table1[i].length; j++) {
      if (table2[i][j] > 0) {
        table1[i][j] = table2[i][j]
      }
    }
  }
}

function fill_rect(table = [[]], left = 0, top = 0, rows = 0, cols = 0, value = 1) {
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      table[top + i][left + j] = value
    }
  }
}

function show_log(table = [[]]) {
  for (let i = 0; i < table.length; i++) {
    console.log(i, table[i].map(v => `${v}`.padStart(2, '0')).join(','))
  }
}

function query_lt(table = [[]]) {
  let targetRow = -1, targetCol = -1
  for (let i = 0; i < table.length; i++) {
    for (let j = 0; j < table[i].length; j++) {
      if (table[i][j] > 0) {
        targetRow = i, targetCol = j
        break
      }
    }
    if (targetRow >= 0) {
      break
    }
  }
  return { top: targetRow, left: targetCol }
}

function flow_layout(metrics=[]){
  const flowTable = gen_empty_table(rows, columns)
  const sortedMetrics = metrics.sort((one, two) => {
    return Math.random() * 10 - Math.random() * 10
  })
  for (let i = 0; i < sortedMetrics.length; i++) {
    const box = sortedMetrics[i]
    if (box.done) continue
    const rst = find_lt(flowTable, box.columns, box.rows, 0)
    if (rst.left < 0) {
      box.top = Math.min(Math.floor((rows - box.rows - 1) * Math.random()), rows - box.rows - 1)
      box.left = Math.min(Math.floor((columns - box.columns - 1) * Math.random()), columns - box.columns - 1)
    } else {
      box.left = rst.left, box.top = rst.top
    }
    box.done = true, box.overlap = rst.left < 0
    fill_rect(flowTable, box.left, box.top, box.rows, box.columns, i + 1)
  }
  return flowTable
}

function layout() {
  console.log('接收到的参数:', props.boxWidth, props.boxHeight, props.cellWidth, props.cellHeight, props.elementMaxWidth, props.grid, props.deepth)
  rows = props.boxHeight / props.cellHeight
  columns = props.boxWidth / props.cellWidth
  showGrid.value = props.grid
  const startTime = new Date().getTime()
  console.log('布局开始:', startTime)
  result_table = gen_empty_table(rows, columns)
  let metrics = do_layout()
  const overlap = metrics.filter(m => m.overlap).length > 0
  if (overlap) {
    // 有遮挡，则将maxWidth调整到最大, 此时应该清除result_table
    result_table = gen_empty_table(rows, columns)
    metrics = do_layout(props.boxWidth, true)
  }
  const duration = new Date().getTime() - startTime
  console.log('布局结束:', duration)
  emit('onLayout', duration)
  nodes.value = metrics
}

function do_layout(referMaxWidth=0, flow=false) {
  if (props.data.length == 0) {
    return
  }
  const rmWidth = referMaxWidth || props.elementMaxWidth
  const metrics = props.data.map(txt => {
    // 将最大宽度设置为动态值，若不需要，则可以设置为0, 这里最大宽度的区间为[elementMaxWidth, 2*elementMaxWidth)
    const delta = rmWidth
    const maxW =  Math.round(Math.random() * delta) + rmWidth
    return measure(txt, maxW)
  }).sort((first, second) => {
    return (first.width + first.height) - (second.width + second.height)
  })
  const area = metrics.map(v => v.rows * v.columns).reduce((p, c) => p + c)
  if (area > rows * columns * 0.75) {
    //占用率很高，完全随机的话效果并不好, 采用flow layout
    console.log(`占用率过高:${area}, ${rows*columns}, 采用flow layout`)
    const t_ = flow_layout(metrics)
    merge_table(result_table, t_)
  } else {
    for (let i = metrics.length - 1; i >= 0; i--) {
      const metric = metrics[i]
      let found = false, target = {left: -1, top: -1, table:[]}
      for (let j = 0; j < props.deepth; j++) {
        target = gen_layout_table(metric.rows, metric.columns, rows, columns, i+1)
        if (!is_cross_over(result_table, target.table)) {
          merge_table(result_table, target.table)
          metric.left = target.left, metric.top = target.top
          found = true
          break
        }
      }
      if (!found) {
        const result = find_lt(result_table, metric.columns, metric.rows)
        if (result.left < 0) {
          console.log(`missed:${metric.text}, ${metric.rows}, ${metric.columns}`)
          // 最终也没有找到，此时可以:
          // 1. 采用flow_layout来代替;
          // 2. 默认交叉
          // 3. 找到剩余最大空间后对metric进行缩放
          // 这里采用2
          merge_table(result_table, target.table)
          metric.overlap = true
          metric.left = target.left, metric.top = target.top
        } else {
          const tmp = gen_empty_table(rows, columns)
          fill_rect(tmp, result.left, result.top, metric.rows, metric.columns, i+1)
          merge_table(result_table, tmp)
          metric.left = result.left, metric.top = result.top
        }
      }
      console.log('尝试random layout')
    }
    const missed = metrics.filter(m => m.overlap).length
    console.log(`共${missed}个未找到相应空间`)
    if (missed > 0) {
      console.log('random layout有重合，再次采用flow layout')
      if (missed > 5) {
        alert(`存在过多未布局的元素, 应减少单词数量`)
      }
      metrics.forEach(v => {
        v.left = -1, v.top = -1, v.overlap = false
      })
      // 未正确布局的过多，可以考虑flow layout
      let tmp
      for (let k = 0; k < 5; k++) {
        tmp = flow_layout(metrics)
        const overlap = metrics.filter(v => v.overlap).length > 0
        if (!overlap) {
          break
        }
      }
      merge_table(result_table, tmp)
    }
  }

  const overlaps = metrics.filter(m => m.overlap)
  overlaps.forEach(m => {
    console.log('存在遮挡:', m.text, m.leftPx, m.topPx)
  })
  calculate(metrics, result_table, flow)
  return metrics
}

function calculate(metrics=[], table=[[]], flow = false) {
  let offset = 0
  for (let i = table.length - 1; i >= 0; i--) {
    if (table[i].reduce((p, c) => p+c) > 0) {
      break
    } else {
      offset++
    }
  }
  const validLine = table.length - offset
  const shouldTranslateRight = table.map(inn => inn[inn.length - 1]).filter(v => v > 0).length == 0
  const distanceR = shouldTranslateRight ? props.cellWidth / 2 : 0
  const delta = (rows / validLine - 1)
  metrics.forEach(metric => {
    const remain = Math.floor(metric.top * delta * props.cellHeight)
    if (flow) console.log('remain1:', remain, metric.top, metric.top * props.cellHeight)
    metric.leftPx = metric.left * props.cellWidth + distanceR
    metric.topPx = metric.top * props.cellHeight + remain
    if (flow) console.log('remain2:', remain, metric.top, metric.topPx)
  })
  if (flow) {
    console.log('偏移:', offset, delta)
  }
}

function draw_grid() {
  const ctx = canvas.value.getContext('2d')
  const dpr = window.devicePixelRatio
  const gridWidth = dpr * props.cellWidth, gridHeight = dpr * props.cellHeight
  ctx.strokeStyle = "red";
  ctx.lineWidth=0.5
  for (let i = gridWidth; i < canvas.value.width; i += gridWidth) {
    ctx.moveTo(i, 0)
    ctx.lineTo(i, canvas.value.height-dpr)
    ctx.stroke()
  }
  for (let i = gridHeight; i < canvas.value.height; i += gridHeight) {
    ctx.moveTo(0, i)
    ctx.lineTo(canvas.value.width-dpr, i)
    ctx.stroke()
  }
}
onMounted(() => {
  nextTick(() => {
    draw_grid()
    layout()
  })
})

function doTouch(node) {
  console.log(node)
}

defineExpose({
  layout,
  nodes
})

</script>

<template>
  <div class="wrapper relative border-1" :style="`width:${props.boxWidth}px;height:${props.boxHeight}px;`">
    <div ref="referBox" class="refer-box absolute" :style="`visibility:hidden;`">
      <div ref="refer" class="refer"></div>
    </div>
    <div class="box-wrapper relative" :style="`width:${props.boxWidth}px;height:${props.boxHeight}px;`">
      <div class="bg-grid absolute" v-show="props.grid" :style="`width:${props.boxWidth}px;height:${props.boxHeight}px;`">
        <canvas ref="canvas" :width="canvasWidth" :height="canvasHeight" :style="`width:${props.boxWidth}px;height:${props.boxHeight}px;box-sizing:border-box;`"></canvas>
      </div>
      <div class="box absolute" :style="`width:${props.boxWidth}px;height:${props.boxHeight}px;`">
        <template v-for="(node, idx) in nodes" :key="idx">
          <div @touch="doTouch(node)" @click="doTouch(node)" class="refer-box absolute z-index-1000" :style="`z-index:1000;left:${node.leftPx}px;top:${node.topPx}px;`">
            <div class="refer" :class="{'border-red': node.overlap}" :style="`max-width:${node.maxW}px;z-index:1000;`">{{ node.text }}</div>
          </div>
        </template>
      </div>
    </div>
  </div>
</template>

<style scoped>
.relative {
  position: relative;
}
.absolute {
  position: absolute;
  z-index: 999;
}
.wrapper {
  box-sizing: border-box;
}
.refer-box {
  left: 0;
  top: 0;
  padding: 0px; /* 调整此处可处理box间距，但同时也会增加box占用的面积 */
  display: inline-block;
  box-sizing: border-box;
}
.refer-box:hover {
  cursor: pointer;
}
.refer {
  display: inline-block;
  word-wrap: break-word;
  font-family: Arial, sans-serif;
  font-size: 15px;
  line-height: 1.2;
  color: black;
  background-color: #cbecbb;
  padding: 10px;
  box-sizing: border-box;
  border: 5px solid rgb(66, 195, 66);
  border-radius: 10px;
}

.border-1 {
  border: 1px solid rgb(108, 188, 108);
}
.border-half {
  border: 0.5px solid rgb(203, 164, 100);
}
.bg-grid {
  box-sizing: border-box;
  /* background-color: red; */
}

.cell {
  box-sizing: border-box;
}
.border-red {
  border-color: red;
  background-color: rgba(243, 137, 137, 0.8);
}
.z-index-999 {
  z-index: 999;
}
.z-index-1000 {
  z-index: 1000;
}
</style>